package com.leetcode_mianshi_150;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        //int value = -1;
        //if (cache.containsKey(key)) {
        //    DLinkedNode node = cache.get(key);
        //    value = node.value;
        //
        //    //由于使用了，所以放到第一位
        //    //删除,remove(node)
        //    removeNode(node);
        //    //添加,add
        //    add(node);
        //
        //    return value;
        //}
        //
        //return value;
        //优化
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部

        removeNode(node);
        add(node);
        return node.value;



    }

    public void put(int key, int value) {


        //if (cache.containsKey(key)) {
        //    DLinkedNode node = cache.get(key);
        //    node.value = value;
        //    //删除,remove(node)
        //    removeNode(node);
        //    //添加,add
        //    add(node);
        //    return;
        //}
        //
        //
        //size++;
        //if (size > capacity) {
        //    //移除头节点，移除缓存
        //    cache.remove(removeHead().key);
        //    //添加到尾部
        //    DLinkedNode node = new DLinkedNode(key, value);
        //    add(node);
        //    cache.put(key, node);
        //    size--;
        //} else {
        //    DLinkedNode node = new DLinkedNode(key, value);
        //    cache.put(key, node);
        //    add(node);
        //
        //}

        //优化
        DLinkedNode node = cache.get(key);

        if (node == null) {
            size++;
            node = new DLinkedNode(key, value);
            cache.put(key, node);
            add(node);
            if (size > capacity) {
                //移除头节点，移除缓存
                cache.remove(removeHead().key);
                size--;
            }
        } else {
                node = cache.get(key);
                node.value = value;
                //删除,remove(node)
                removeNode(node);
                //添加,add
                add(node);
        }
    }

    public DLinkedNode removeHead() {
        DLinkedNode node = head.next;
        head.next = node.next;
        node.next.prev = head;
        return node;
    }

    public void add(DLinkedNode node) {
        node.next = tail;
        node.prev = tail.prev;
        node.prev.next = node;
        tail.prev = node;
    }

    public void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }


}




class Test{
    public static void main(String[] args) {
        LRUCache obj = new LRUCache(2);
        obj.put(1, 1);
        obj.put(2, 2);
        obj.get(1);
        obj.put(3, 3);
        obj.get(2);
        obj.put(4, 4);
        obj.get(1);
        obj.get(3);
        obj.get(4);
    }
}